package basic.study.algorithms.solution.DynamicProgramming;

/**
 * @author Kevin
 * @date 2020/2/19 19:58
 * 计算最长公共子串长度
 *
 * 如果：a[i]==b[j]，那么：max_lcs(i, j)就等于：
 * max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))；
 *
 * 如果：a[i]!=b[j]，那么：max_lcs(i, j)就等于：
 * max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))；
 *
 * 其中max表示求三数中的最大值。
 */
public class SearchEngine2 {
    public int lcs(char[] a, int n, char[] b, int m) {
        int[][] maxcls = new int[n][m];
        for (int j = 0; j < m; j++) {//初始化第0行：a[0..0]与b[0..j]的maxlcs
            if (a[0] == b[j]) maxcls[0][j] = 1;
            else if (j != 0) maxcls[0][j] = maxcls[0][j-1];
            else maxcls[0][j] = 0;
        }
        for (int i = 0; i < n; i++) {//初始化第0列：a[0..i]与b[0..0]的maxlcs
            if (a[i] == b[0]) maxcls[i][0] = 1;
            else if (i != 0) maxcls[i][0] = maxcls[i-1][0];
            else maxcls[i][0] = 0;
        }
        for (int i = 1; i < n; i++) {//填表
            for (int j = 1; j < m; j++) {
                if (a[i] == b[j])  maxcls[i][j] = max(maxcls[i-1][j], maxcls[i][j-1], maxcls[i-1][j-1]+1);
                else maxcls[i][j] = max(maxcls[i-1][j], maxcls[i][j-1], maxcls[i-1][j-1]);
            }
        }
        return maxcls[n-1][m-1];
    }

    private int max(int x, int y, int z) {
        int max = Integer.MIN_VALUE;
        if (x > max) x = max;
        if (y > max) y = max;
        if (z > max) z = max;
        return max;
    }
}
